//
// Description: 1871. 跳跃游戏 VII
// Created by Loading on 2021/8/14.
//

#include <bits/stdc++.h>

using namespace std;

bool canReach(string s, int minJump, int maxJump) {
    /* 将 dp 数组和前缀和数组均错开一位，无需特判 0 的情况 */
    // dp[i] 表示能否到达 i 位置，dp[i] 取 0 或 1
    vector<int> dp(s.size() + 1);
    // dp 数组的前缀和
    vector<int> sum_prefix(s.size() + 1);
    dp[1] = 1;
    sum_prefix[1] = 1;
    for (int i = 2; i <= s.size(); ++i) {
        // 需要增加条件 i - minJump >= 1，1 代表下标为 0 的位置，最少跳跃 minJump 单位
        if (s[i - 1] == '0' && i - minJump >= 1) {
            int left = max(i - maxJump, 1);
            int right = i - minJump;
            // [max(i - maxJump, 1), i - minJump] 区间存在 1，也就是区间和 > 0，即为可以到达 i 处
            if (sum_prefix[right] > sum_prefix[left - 1]) {
                dp[i] = 1;
            }
        }
        sum_prefix[i] = sum_prefix[i - 1] + dp[i];
    }

    return dp[s.size()];
}

int main() {
    string s = "011010";
    int minJump = 2;
    int maxJump = 3;
    bool res = canReach(s, minJump, maxJump);
    cout << res << endl;
}